package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-03-02 21:13
 **/
public class LeetCode564 {

    public String nearestPalindromic(String n) {
        long src = Long.parseLong(n);
        List<Long> candidates = getCandidates(n);
        long ans = - 1;
        for (Long candidate : candidates) {
            if (candidate != src) {
                if (ans == -1 ||
                    Math.abs(candidate - src) < Math.abs(ans - src) ||
                    Math.abs(candidate - src) == Math.abs(ans - src) && candidate < ans) {
                    ans = candidate;
                }
            }
        }
        return String.valueOf(ans);
    }

    //1.用原数的前半部分替换后半部分得到的回文整数。
    //2.用原数的前半部分加一后的结果替换后半部分得到的回文整数。
    //3.用原数的前半部分减一后的结果替换后半部分得到的回文整数。
    //4.为防止位数变化导致构造的回文整数错误，因此直接构造 999999…999 和 100…001 作为备选答案。

    List<Long> getCandidates(String num) {
        int len = num.length();
        //数位变化的两种情况
        List<Long> candidates = new ArrayList<Long>(){{
            add((long) Math.pow(10, len - 1) - 1);
            add((long) Math.pow(10, len) + 1);
        }};
        long half = Long.parseLong(num.substring(0, (len + 1) / 2));
        for (long i = half - 1; i <= half + 1; ++i) {
            StringBuilder builder = new StringBuilder();
            //前半
            String prefix = String.valueOf(i);
            builder.append(prefix);
            //将前半翻转
            StringBuilder suffix = new StringBuilder(prefix).reverse();
            //根据len的奇偶调整字符串裁剪的位置
            builder.append(suffix.substring((len & 1)));
            candidates.add(Long.parseLong(builder.toString()));
        }
        return candidates;
    }

}
